life.txt
S. Weyer
1/1/96

Life is a mathematical simulation game described by John Conway in
Scientific American in Oct. 1970.

Several rules are used to create a next generation from a cell's 8 neighbors:
- Survival: A cell with 2 or 3 neighbors survives.
- Death: A cell with 1 or less, or 4 or more neighbors, "dies".
- Birth: An empty cell with exactly 3 neighbors will be "born".

Keywords: Life, cellular automata, Newt, mathematical simulation, Conway


Recent changes [Life 1.4] (1/1/96):
- NOS 2.0 compatible
- integrates 6 display/speed options (selectable via "method" picker)
  2 different representations: array or bitmap
  3 different styles: object-oriented, inline, native(RISC) code
- adds "gen" picker for disabling gen# update or doing timing
- line gesture to fill area, scrub gesture to erase area
- created with Newt Development Environment
- includes Newt source

Contents:
- life.txt   -- this file
- Life14.pkg -- a ready-to-install package (created by Newt)
- life.nwt   -- Newt source
- life.bit   -- LifeIcon
(Mac format text file in .sit/.hqx archives; DOS text in .zip archive)

The "game of Life" is freeware and may be distributed freely as long as all of
these files are included and unmodified.  You are free to make modifications
for your own use. Copyright 1994-96, S. Weyer. All Rights Reserved Worldwide.

----------
Development and "Newt"

If you would like to construct and modify Life directly on your Newton,
obtain the latest version of

- "Newt" (newt-devenv-32)  -- an environment for developing applications
  saving as packages directly on your Newton

- "Slurpee" (slurpee-17) a text/data transfer utility (both shareware)

from your favorite Newton server/archive (internet (AMUG, uiowa,...), AOL,
Compuserve, eWorld). See "Develop" and "Author" help pages. Contact me if you
have trouble finding Newt, using it initially, or have questions about
registering it.

Registered Newt users receive a 80+ pp. introductory manual, and access to
190+ examples. This includes NewtPFB (an interactive tutorial, similar to
NewtATut), and LifeCnst.pkg plug-in for building versions of Life with
native code.

For more development details, see "Building and Transferring Life" (later).

----------
Revision History:
Life 1.4 (1/1/96)
  (see above)

Life 1.3N & life13.nwt (8/11/95) [non-public releases]
- [very similar to Life 1.2B & life12b1.nwt -- available earlier to Newt users]
- faster generation from native code for several methods
- for increased speed, suppress Gen: refresh by tapping on it

Life 1.2B (11/12/94)
- limits width of universe to 30 (width of NewtonScript integer)
- caches/operates on rows as longint (or NIL) rather than bitmap directly
- inlines inner-loop getCell accesses for greater speed (vs. clarity)
- does not display the empty border columns/rows
- numbers x (bit) positions from right to left
- handles scrub gesture for Clear (see LifeDraw:viewGestureScript)
- selectable grid sizes (see gridSize)
- generates faster (1.5 - 3.5x Life 1.2) and allows larger grids
  by using a bitmap data structure for storage and drawing

Life 1.2 (11/12/94)
- modifies symbol names/program structure to be more consistent with 1.2B
- fixes button highlighting glitch (sibling order)

Life 1.1 (10/15/94)
- uses 0/1 for cell values rather than nil/true
- allows patterns to be selected/added
- adds a grid (when stopped)

Life 1.0 (9/18/94)
- adds a "Clear" and "Next" button
- adds a generation counter.
- adds a "Repeat" button -- which invokes "Next" in the background until
  you tap "Stop" (or all cells are empty)
- adds an "Info" button and help book
- avoids allocating/examining empty rows/columns where possible to
  improve speed drawing and generating

Life "0.1" (3/94)
- see "Life with NewtonScript" by David Betz in Byte, March 1994, pp. 191-194.
This article provided inspiration, an initial framework and a few main methods.

The early versions are quite usable for small patterns, but not blindingly
fast for more sparse or spreadout patterns -- the emphasis is on the complete
application and learning programming.  There is also another source version
life12b.nwt (available to registered Newt users) which is uses the same basic
bitmap representation as life13.nwt, but is slower and perhaps more
understandable since it is less heavily optimized).

Possible future enhancements:
- allow patterns to be saved in/retrieved from a soup
- save preferences for grid size, etc.

If you would like to encourage me to develop and distribute this and other
examples, I encourage you to register Newt (kind words also appreciated).

----------
Using Life

Tap the info button to access the built-in help book.

Some classic patterns to try (some in pattern picker):
  OOO     (blinker -- flips)

   O
  O       (glider -- moves down&left 1 in 4 steps)
  OOO

  OO
  OO      (block -- stable)

   OO
  O  O    (beehive -- stable)
   OO

    
  OOOOO   (turns into "traffic lights" (4 blinkers) in 9 steps)

 OOOOOOO  (turns into "honey farm" (4 beehives) ...)

OOOOOOOOO (double traffic lights...)

----------
Transferring and Building Life

Use your favorite transfer mechanism to move the text from your desktop system
to the Newton Notepad. This file is formatted to be used most easily with
Slurpee.  ----- delimits separate notes.

To build the Life application, install Newt (3.2 is the latest version at
time of this release). If you would like to save the application as the
package to run it standalone later, also install the NewtPack plug-in, which
comes with Newt. If you would like to use native (faster) methods for Life
in Newt, install the LifeCnst.pkg plugin -- this way you could customize the
application while also gaining extra performance by borrowing those methods
from the Life "library". [LifeCnst available to registered Newt users]

If you would like to use the Life icon, transfer the life.bit file with Slurpee,
and uncomment the line inside _package in the life.nwt source.

Start Newt, select the folder at top where you stored the source.

If you are low on heap, you may want to "comment out" the two long in-line
methods: Life._arrI.nextGeneration and Life.bitI.nextGeneration
by changing the names, e.g.,
  xLife._arrI.nextGeneration
  xLife._bitI.nextGeneration
(this will remove them from the build process, and Life will just
use the generic nextGeneration method)
(when you're done, browse to #newObject to free up a little more space)

Tap Expr, select :doObj('build,'Life), tap Eval

Some simple modifications you might try:
- add other patterns in patternPicker.patterns array (and names in labelCommands)
- add other pages to the helpbook
- change MakeOval to MakeRect in drawDots
- change the rules (nextGeneration)

Note: constants such as vfFillWhite can be used, but this requires additional
plug-ins, e.g., viewCnst.pkg to define these at development time.

If you would like to run your version of the Life application later without
having to recompile the sources in Newt, and you have NewtPack installed,
tap the Save button (in Eval Controls) when Life is open. (or Eval 
:saveApp(Life)).

If you have further optimizations that you would like to contribute, feel free
to send them to me, and if I incorporate them, you'll be recognized.

----------
Implementation:

This version of Life show several different implementations.
There are two basic mechanisms: "arr" and "bit".
- "arr" refers to the internal representation of rows as arrays of cells;
the drawing is done cell-by-cell. [similar to an earlier version -- Life 1.2,
and to Betz' Byte article].
- "bit" refers to the internal representation of rows as words in a bitmap;
the drawing is done directly with the bitmap. [similar to Life 1.2B].

There are three variations for each: "", "I", "N",
- "".  default. more object-oriented -- uses same :nextGeneration method
- "I". Inline. :nextGeneration inlines (i.e., substitutes definitions for)
  :getCell,:getRow, :setCell,:setRow methods
- "N". Native. :nextGeneration is native (RISC) compiled code.
  For development, this requires you install the LifeConst.pkg plug-in so that you
  can use/copy the constants while still modifying the main application on your Newton

So, the source supports 6 versions:
- "arr" uses arrays for representing rows; it is written in a very object-oriented style;
  in fact, it uses the same :nextGeneration method as "bitO".
- "arrI" same as "arr" but in-lines :nextGeneration
  (i.e., substitutes definitions for :getCell,:getRow, :setCell,:setRow methods).
- "arrN" uses native code for :nextGeneration
- "bit" uses a bitmap for representing and drawing cells.
  it uses the same generic :nextGeneration method as "arrO"
- "bitI" same as "bit" but inlines :nextGeneration
- "bitN" uses native code for :nextGeneration and :makeUniverse
   (the NewtonScript is identical to "bitI" but without declarations;
   I did not include the declarations here -- although they are ignored
   by the Newton compiler for NOS 2.0, the 1.x compiler generates errors).

The Life application and package was created entirely with the Newt
Development Environment. (LifeCnst.pkg plug-in was created with NTK).

----------

Objects:

Life -- the application (floating view)
  [split into several sections to make editing on Newton more manageable]
drawArea -- an embedded view to handle drawing
titleObj -- title at top of Life view
status -- status bar at bottom of Life view
clearButton, nextButton, repeatButton, zhelpButton -- embedded in status
gridPicker -- picker for selecting grid size
methPicker -- picker for switching between various "arr" and "bit" methods
patternPicker -- picker for selecting patterns
genPicker -- picker for update/timing, generation counter
helpBook -- help book data structure
helpView -- dynamic "Tiny Tim" help reader view
ButtonBounds -- development-time method for computing location of status buttons

"method frames"
there are 6 frames that contain 9 methods each that define the representation,
computation and display for the six versions included: "arr", "arrI", "arrN", "bit", "bitI", "bitN".
when the user makes a choice in "method picker", these are copied into the current
Life application (view). [original "arr" defs are still in the app template]

Generally, there are many ways to write "nextGeneration". I chose one that
hopefully isn't too hard to follow, works for both the array and bitmap
representations, and performs reasonably well. With some INT declarations
put in, the same version produces "bitN" which is quite fast.  I would be
interested in any faster algorithms or programming tricks also. (see "Timing"
below).

-----
Coordinates:

To maximize performance for the "bit" implementation, I constrained the x
coordinate to be between 0 and 29 (numbered from right to left), to
correspond to bit positions in a NewtonScript integer ("long"); the "array"
implementation follows these conventions also in order to share methods. I
have other implementations that can access multiple longs, but large grids
are difficult to display and impractical to compute anyway.  The y
coordinate is numbered from top to bottom. Cells are square.

-----

You can speed up computation somewhat by selecting "gen <0>".
This indicates that the generation counter should not be updated.

-----
Benchmarks

To do benchmarks, I would recommend saving the application first. This
maximizes the amount of heap that is available (and minimize the amount
of time that Life spends in gc (garbage collection)).

In order to see timing results printed, do one of the following:
- connect the NTK Inspector
- open Slurpee (in Inspect? mode) with a terminal emulator
  [you can drag Slurpee off right screen edge; also toward bottom
  so it's not totally on grid]
- open Newt (and turn on Print?)

Select "gen <time:40>" to do 40 iterations of a pattern.

Draw your pattern, tap Repeat.

time: <ticks = 60ths of a sec> will appear.

note: generation counter is set to 0
after Clear, new method picked, or timing complete


Two simple patterns that indicate roughly the performance profiles
of these different methods.

- glider. small dynamic pattern

- 4 blocks (one in each corner of grid). maximize number of rows examined


I used a 26x29 grid. I did two tests for each data point and took the
average. I tested on a MP100(1.3), MP110(1.3) and MP120(2.0).

											xx	...	xx
											xx		xx
				 x							...		
				x							xx		xx
				xxx							xx		xx
				glider						corners4								

		100		110		120			100		110		120
		----	----	----		----	----	----
arr		1100	1030	 472		3775	3700	1058
arrI	 785	 750	 385		2374	2330	 683
arrN 	 575	 520	 405		1336	1320	 708
bit      930	 940	 362		3760	3575	 962
bitI     695	 682	 284		2487	2345	 573
bitN     237	 215	 213		 243	 220	 216


Some initial observations:
(of course, it's dangerous to draw any very general conclusions
based on such few data points; your mileage may vary depending on
the patterns you try, amount of heap, etc.):

- large patterns generally take much longer time (though bitN is almost constant)
- the NOS 2.0 NewtonScript interpreter can be much (2x-3x) faster than 1.x
- some native code (arrN) can be slower on 2.0! (an anomaly worth investigating)
  advantage of bitN much less on 2.0
- MP100 a little slower than MP110

I'd be interested in other results/observations on these and
other algorithmic variations.

